The invention relates to an array of quantum bits known as a quantum computer. More specifically, it relates to the generation of the instruction sequences that are used to manipulate such an array.
This invention deals with quantum computers. A quantum computer is an array of quantum bits (qubits) together with sonic hardware for manipulating these qubits. Quantum computers with only a few bits have already been built. For a review of quantum computers, see DiV95: D. P. DiVincenzo. Science 270, 255 (1995). See also Ste97:A. M. Steane, Los Alamos eprint http://xxx.lanl.gov/abs/quant-ph/9708022.
This invention also deals with Quantum Bayesian (QB) nets. QB Nets are a method of modeling quantum systems graphically in terms of network diagrams. For more information, see Tuc95: R. R. Tucci. Int. Jour. of Mod. Physics B9, 295 (1995). See also Tuc98: U.S. Pat. No. 5,787,236.
In classical computation and digital electronics, one deals with sequences of elementary instructions (instructions such as AND, NOT and OR). These sequences are used to manipulate an array of classical bits. The instructions are elementary in the sense that they act on only a few bits (usually 1, 2 or 3) at a time. Henceforth, we will sometimes refer to sequences as products and to instructions as operations, operators, steps or gates. Furthermore, we will abbreviate the phrase xe2x80x9csequence of elementary operationsxe2x80x9d by xe2x80x9cSEOxe2x80x9d. In quantum computation, one also deals with SEOs, but for manipulating qubits instead of classical bits.
This invention comprises a classical computer running a computer program that expresses the information contained in a QB net as a SEO. One can then run these SEOs on a quantum computer. Of course, QB nets can and have been run entirely on a classical computer. (See the software program called xe2x80x9cQuantum Fogxe2x80x9d, produced by the Artiste company (www.ar-tiste.com)). However, because of the higher speeds promised by quantum parallelism, one expects QB nets to run much faster on a quantum computer.
With classical computers, one usually writes a computer program in a high level language (like Fortran, C or C++). A compiler then expresses this as a SEO for manipulating bits. In the case of quantum computers, a QB net may be thought of as a program in a high level language. This invention is like a xe2x80x9cquantum compilerxe2x80x9d in the sense that it can take a QB net input, and re-express it as a SEO that can then be used to manipulate qubits.
This invention shows how to reduce a QB net into a SEO by a two step process. First, express the information contained in the QB net as a sequence of unitary operators. Second, express each of those unitary operators as a SEO. An appendix to this document contains the C++ source code of a computer program called xe2x80x9cQubiter.1.0xe2x80x9d. In its current version (1.0), Qubiter can decompose into a SEO only the simplest non-trivial kind of QB net: a single unitary matrix, or, equivalently. 2 connected nodes. Future versions of Qubiter are planned that will take an arbitrary QB net as input, and return as output a SEO for running a quantum computer.
QB nets are to quantum physics what Classical Bayesian (CB) nets are to classical physics. For a review of CB nets, see Nea9O: Richard E. Neapolitan, Probabilistic Reasoning in Expert Systems: Theory and Algorithms (Wiley, 1990). See also Pea88: Judea Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (Morgan Kaufmann, Palo Alto, 1988). CB nets have been used very successfully in the field of artificial intelligence (AI). Thus, we hope and expect that some day QB nets, running on quantum computers, will be used for AI applications. In fact, we believe that quantum computers are ideally suited for such applications. First, because AI tasks often require tremendous power, and quantum computers seem to promise this. Second, because (quantum computers are plagued by quantum noise, which makes their coherence times short. There are palliatives to this, such as quantum error correction (See the review Ste97). But such palliatives come at a price: a large increase in the number of steps. The current literature often mentions factoring a large number into primes as a future use of quantum computers (See the review Ste97). However, due to noise, quantum computers may ultimately prove to be impractical for doing long precise calculations such as this. On the other hand, short coherence times appear to be a less serious problem for the types of calculations involved in AI. The human brain has coherence times too short to factor a 100 digit number into primes, and yet long enough to conceive the frescoes in the Sistine Chapel. We do not mean to imply that the human brain is a quantum computer. An airplane is not a bird, but it makes a good flyer. Perhaps a quantum computer, although not a human brain, can make a good thinker.
To our knowledge, nobody else has invented a method of reducing an arbitrary QB net to a SEO for running a quantum computer. It""s true that previous workers (See Bar95: A. Barrenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. H. Smolin, H. Weinfurter, Physical Review A 52, 3457 (1995)) have described a method for reducing a single unitary operator into a SEO. But our method for doing this is significantly different from theirs. Their method is based on a mathematical technique described in Rec94: M. Reck and A. Zeilinger, Physical Review Letters 73, 58 (1994). Our method is based on a mathematical technique called the CS Decomposition, to be described later. For a review of the CS decomposition, see Pai94: C. C. Paige, M. Wei, Linear Algebra And Its Applications 208, 303 (1994). Our CS method for reducing unitary matrices has inherent binary symmetries that make it easy to apply to qubit systems, which also possess binary symmetries. The method of Bar95 possesses no such symmetries. For this reason, we believe our method to be superior to theirs.
The main goal of the invention is to provide a new method for generating the SEOs that are used to manipulate a quantum computer. This goal is achieved by means of a classical computer running a computer program that takes as input a QB net, and returns as output the desired SEO.
A related goal of the invention is for said computer program to serve as a blueprint that future workers can modify and enlarge.
A related goal is to allow users to run QB nets on a (quantum instead of a classical computer. The QB nets could be used, for example, to do AI tasks such as decision making.
A quantum computer is an array of quantum bits (qubits) together with some method for manipulating these qubits. Quantum Bayesian (QB) nets are a method of modeling quantum systems graphically in terms of network diagrams.
This invention comprises a classical computer that runs a computer program. The program takes a QB net and decomposes it into a sequence of elementary operations (SEO). Such a sequence can be used to manipulate a quantum computer.
This invention shows how to reduce a QB net into a SEO by performing four steps: (1) Find eras. (2) Insert delta functions. (3) Find unitary extensions of era matrices. (4) Decompose each unitary matrix into a SEO.
In step (1), we partition the set of nodes of the QB net into subsets called eras. All nodes in a given era xe2x80x9coccur at roughly the same timexe2x80x9d. We also assign a matrix to each era.
In step (2), we pad the era matrices of step (1) with delta functions so that the resultant era matrices can be multiplied by each other.
In step (3), we extend the era matrices of step (2) (by adding rows and columns) so that the resultant era matrices are all unitary and of the same size.
In step (4), we reduce into a SEO each of the unitary era matrices of step (3). Step (4) is based on the CS Decomposition Theorem. This theorem asserts that: given a unitary matrix U, if we partition it into 4 blocks U0, U1, U2, U3 of the same size, then one can express each Uk, k where kxcex5{0, 1, 2, 3}, as a product LkDkRk, such that Lk and Rk are unitary matrices and Dk is diagonal. Since the matrices Lk and Rk are unitary one can apply the CS Decomposition Theorem to them next. One can continue to apply the CS Decomposition Theorem to the unitary matrices generated in previous steps. In this way, one can express the original matrix U as a product of matrices of a type that we call xe2x80x9ccentral matricesxe2x80x9d. We show how to express any central matrix as a SEO.
An appendix to this document contains the C++ source code of a computer program called xe2x80x9cQubiter1.0xe2x80x9d. In its current version (1.0), Qubiter can decompose into a SEO only the simplest non-trivial kind of QB net: a single unitary matrix, or, equivalently, 2 connected nodes. Future versions of Qubiter are planned that will take an arbitrary QB net as input, and return as output a SEO for running a quantum computer.